googologywikiaorg-20200223-history
User blog:B1mb0w/Deeply Nested Ackermann
Deeply Nested Ackermann The Deeply Nested Ackermann function (signified with a lowercase d) is defined by generalizing the Modified Ackermann Function MA() with a variable input parameter array: \(d(x_1,x_2,x_3,x_4, ... ,x_n)\) Rules for the d function are similar to MA function rules but generalised as follows: \(d() = 0\) This is a null function that always returns zero. \(d(m) = m+1\) This is equivalent to MA(0,m) The next example is equivalent to the \(MA(m,n)\) function. \(d(m,n) = MA(m,n)\) And the same rules apply: \(d(m,n)\) defined as: ◾ \(n+1\) if m=0 , ◾ \(d(m−1,d(m-1,m))\) if n=0 , or ◾ \(d(m−1, d(m,m−1))\) otherwise. For 3 parameters, the rules are generalised and extended as follows: \(d(m_1,m_2,m_3)\) defined as: ◾ \(d(m_{2},m_{3})\) if \(m_1=0\) , ◾ \(d(m_1−1, d(m_1,m_2-1), d(m_1,m_2,m_3-1))\) if \(m_1>0\) , \(m_2>0\) and \(m_3>0\) ◾''but'' \(d(m_1,m_2-1)\) is substituted by \(d(m_1-1,m_1)\) if \(m_2=0\) ◾''and'' \(d(m_1,m_2,m_3-1)\) is substituted by \(d(m_1,m_2-1,m_2)\) if \(m_3=0\) ◾''or'' \d(m_1,m_2,m_3-1)\) is substituted by \(d(m_1-1,m_1,m_1)\) if m_2=0 and m_3=0 General Example Instead of giving an example for \(d(x_{1},x_{2},x_{3},x_{4})\) next, it is actually easier to follow the general example for: \(d(x_{1},x_{2},x_{3},x_{4}, ... ,x_{n})\) defined as this deeply nested function: \(d(x_{1}-1, d(x_{1},x_{2}-1), d(x_{1},x_{2},x_{3}-1), d(x_{1},x_{2},x_{3},x_{4}-1), ..., d(x_{1},x_{2},x_{3},x_{4}, ... ,x_{n}-1)\) The only substitution rules that need to be followed are: Leading Zeros rule L1. \(d(0,0, ...,0,x,y,z)\) is substituted for \(d(x,y,z)\) in all cases Trailing Zeros rule T1. \(d(x,y,z,0,0, ... ,-1)\) is substituted for \(d(x,y,z-1,z,z, ... ,z)\) in all cases Calculated Examples d() = 0 This is a null function that always returns zero. d(3) = 4 This is the successor function d(1,2) = 5 This is the same as MA(1,2) which is equivalent to MA(1,b) = b+3 d(1,0,0) Is the first non trivial calculation and expands as follows: = d(0, d(0,1), d(0,1,1)) then apply the Leading Zeros rule = d( d(1), d(1,1)) = d(2, 4) = 20 This is the same as MA(2,4) which is equivalent to MA(2,b) = 3*b+8 d(1,0,1) expands as follows: = d(0, d(0,1), d(1,0,0)) then apply the Leading Zeros rule = d( d(1), d(1,0,0))) = d(2, 20) = 68 This is the same as MA(2,20) which is equivalent to MA(2,b) = 3*b+8 It can be shown that d(1,0,c) is equivalent to but much greater than > 3^(c+2) More Calculated Examples d(1,1,0) expands as follows: = d(0, d(1,0), d(1,0,1)) from the above examples we know this is equal to = d(3, 68) This is the same as MA(3,68) which is equivalent to MA(3,b) >> 3^(b+3) d(1,2,0) expands as follows: = d(0, d(1,1), d(1,1,2)) from the above examples we know this is equal to = d(4, 3^(2+3)) This is equivalent to but much greater than >> 3^^(b+70) My calculations show that d(1,b,0) is equivalent to but much greater than >> 3^^ ... b arrows ... ^^(b+70) Some Comparisons d(3, 0) = 59 d(3, 9) >> 1,000,000 d(3, 206) >> Googol d(4, 0) = d(3, 5099) >> 3^(5099+3) d(1,1,0) = d(3, 68) << Googol d(1,1,1) = d(d(1,0), d(1,1,0)) = d(3, d(3, 68)) >> 3^3^(68+3) << Googolplex \(d(4,2) >> d(1,1,2) = d(d(1,0), d(1,1,1) >> d(3, 3^{3^{68+3}}) >> Googolplex\) d(1,3,0) >> d(6,0) >> g1 where g64 is Graham's number d(1,4,0) >> d(6, 3^^^^3) >> 3^^^^3^^^^3 = 3^^^^^3 d(1,4,1) >> d(6, d(1,4,0)) and one more d(2,0,0) = d(1,d(1,2),d(1,1,2)) >> d(1, 5, 3^^72) Another Comparison The general rule for comparing d functions with 2 input parameters is: \(d(x,y) = d^{y+2}(x-1,x)\) Other general rules for comparing d functions with 3 and 2 input parameters are: d(1,3,z) >> d(6,z-1) d(1,y,z) >> d(y+3, z-1) d(2,0,z) = d(1, d(1,2), d(2,0,z-1)) >> d( d(1,2)+3 , d(2,0,z-1) -1) >> d(8,z) Comparison Rule The growth rate of the d function is comparable to the Fast-growing hierarchy . Here are some comparisons: \(d(x,y) = d(x-1, d(x,y-1)) = d^{y+2}(x-1,x)\) \(f_x(y) = f_{x-1}^{y}(y)\) \(f_x(y)\) is greater than \(d(x,y)\) because \(f_2(y) = 2.2^y\) and \(d(2,y) = 3.y + 8\) and both growth functions recursively grow at the same rate for greater values of x. So we can use this Comparison Rule: C1. \(f_x(y+2) << d(x+1,y)\) because \(f_{x-1}^{y+2}(y+2) << d^{y+2}(x,x+1)\) and every \(d(x,n) >> f_{x-1}(n)\) by a minimum of a factor of 3 to 2 for any n. This is not obvious because comparing the last nested function we get \(f_{x-1}(y+2) << d(x,x+1)\) in the case y>x+1, the f function dominates and the d(x,) function growth rate may not be fast enough to compensate, especially when y >> x. Proof Let \(f_{x-1}^r(y) >> d^r(x,x+1)\) be any case where the f function is dominating the d function. When this is true then because the d(x,) function growth rate dominates, then it must be true that \(f_{x-1}(y) >> d(x,x+1)\) and: \(f_{x-1}(y) = d(x,x+1) + a_0\) \(d(x,n) >> f_{x-1}(n)\) by a minimum of a factor of 3 to 2, so if \(f_{x-1}^2(y) >> d^2(x,x+1)\) then \(a_0\) must have a minimum size. \(2.f_{x-1}(y) = 2.(d(x,x+1) + a_0) >> 3.d(x,x+1)\) so \(a_0 >> 3.d(x,x+1)/2\) lets assume \(a_0 = 3.d(x,x+1)/2 + a_1\) At this point we have prooved that if r>=2 then y will be >=r. Lets calculate some trivial examples: \(f_0(y) = d(1,2) + a_0 = d(1,2) + 3.d(1,2)/2 + a_1 >> 5.d(1,2)/2 = 5*5/2 = 12.5\) so \(y >> 11\) \(f_1(y) = d(2,3) + a_0 = d(2,3) + 3.d(2,3)/2 + a_1 >> 5.d(2,3)/2 = 5*17/2 = 42.5\) so \(y >> 3\) and in all other cases y>x+1 from the comparison rule, so y>3. But how big must \(a_1\) be for r=3 such as \(f_{x-1}^3(y) >> d^3(x,x+1)\). \(2.2.f_{x-1}(y) = 4.(d(x,x+1) + a_0) = 4.(d(x,x+1) + 3.d(x,x+1)/2 + a_1) = 7.d(x,x+1) + 4.a_1) >> 3.3.d(x,x+1)\) and \(7.d(x,x+1) + 4.a_1) >> 9.d(x,x+1)\) so \(a_1 >> d(x,x+1)/2\) lets assume \(a_1 = d(x,x+1)/2 + a_2\) and \(a_0 = 2.d(x,x+1) + a_2)\) and lets calculate: \(f_2(y) = d(3,4) + a_0 = d(3,4) + 2.d(3,4) + a_2 >> 3.d(3,4) = 3*5099 = 15297\) so \(y >> 10\) and in all other cases y>x+1 from the comparison rule, so y>6. Completion of Proof This proof by induction shows that each iteration of calculating \(a_n\) for r>=4 will require the minimum bound for y to increase by >=1 every time. Which means the requirement that y>=r must change to y>r and: \(f_x(y+2) << d(x+1,y)\) for all cases including any examples of \(f_{x-1}^r(y) >> d^r(x,x+1)\) Graham's Number The d function can reach \(g_1\), where \(g_{64} = G\) (Graham's number), relatively quickly. As shown above \(d(1,3,0) >> g_1\) . \(g_0 = 4\) and \(g_1 = 3 \uparrow\uparrow\uparrow\uparrow 3 << f_5(3) = f_{g_0}(3)\) \(g_2 << f_{g_1}(3)\) and likewise till \(G = g_{64} << f_{g_{63}}(3)\) In the fast-growing hierarchy, Graham's Number can be shown to be less than \(f_{\omega+1}(64) = f_{\omega}^{64}(64)\). G is closer to still less than f_{\omega}^{64}(5) . We need d functions with many more input parameters to reach G (Graham's Number). d(6,1) >> f_5(3) >> g1 d( d(6,1), 1) >> g2 d(6,1,1) we will get d(6,1) nested in its long expansion and therefore d(6,1,1) >> g2 by a very great amount. We can reach g3 by moving to 4 input parameters d(6,1,1,1) >> g3 We finally reach G (Graham's Number) with 64 input parameters d(6,1,1,1, ..., 1,1) >> G Growth Rate The growth rate for \(d(x,y)\) is comparable to \(f_{\omega}(n)\) The growth rate for \(d(x_1,x_2,x_3,x_4,...,x_n)\) is comparable to \(f_{\omega+1}(n)\) Next To get more impressive growth growths, we can create a strong version of this function. My next blog post introduces the Strong D Function based on the above (weak) d function. Category:Blog posts